//@原文链接：
//https://blog.csdn.net/ITSOK_123/article/details/124384635
//栈实现1：
class Solution {
public:
    bool isValid(string str) {
        int n=str.length();
        if(n%2==1) return false;
        stack<char> s;
        for(char c:str){
            if(c=='[' || c== '{' || c=='('){
                s.push(c);
            }
            else{
                if(s.empty()) return false;
                if(c==']' && s.top()!='[')
                    return false;
                 if(c=='}' && s.top()!='{')
                    return false;
                 if(c==')' && s.top()!='(')
                    return false;
                s.pop();
            }
        }
        return s.empty();
    }
};

//栈实现2:
class Solution {
public:
    bool isValid(string str) {
        int n=str.length();
        if(n%2==1) return false;
        stack<char> s;
        for(char c:str){
            if(c=='{') 
                s.push('}');
            else if(c=='[')
                 s.push(']');
            else if(c=='(') 
                s.push(')');
            else if(s.empty() || c!=s.top()){
                return false;
            }
            else s.pop();
        }
        return s.empty();
    }
};
